package com.zhouxianglh.p301;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 301. 删除无效的括号
 *
 * @author zhouxianglh
 */
public class Solution {
    public static void main(String[] args) {
        // System.out.println(removeInvalidParentheses(")("));
        // System.out.println(removeInvalidParentheses("()())()"));
        // System.out.println(removeInvalidParentheses("(a)())()"));
        System.out.println(removeInvalidParentheses(")()("));
    }

    public static List<String> removeInvalidParentheses(String s) {
        List<String> list = new LinkedList<>();
        char[] chars = s.toCharArray();
        char[] charArr = Arrays.copyOf(chars, chars.length);
        if (check(charArr)) {
            list.add(s);
            return list;
        }
        int level = 1;
        while (true) {
            if (level == charArr.length) {
                list.add(s.replace("(", "").replace(")", ""));
                return list;
            }
            foop(charArr, list, 0, level);
            if (list.size() != 0) {
                return list;
            }
            level++;
        }
    }

    public static void foop(char[] charArr, List<String> list, int start, int level) {
        for (int i = start, j = charArr.length; i < j; i++) {
            char tempChar = charArr[i];
            if (tempChar != '(' && tempChar != ')') {
                continue;
            }
            charArr[i] = ' ';
            if (check(charArr)) {
                String result = new String(charArr).replace(" ", "");
                if (!list.contains(result)) {
                    list.add(result);
                }
            }
            if (level > 1) {
                foop(charArr, list, i + 1, level - 1);
            }
            charArr[i] = tempChar;
        }
    }

    public static boolean check(char[] chars) {
        //这里可以优化,统计括号数即可,无语操作数组
        // res = 0
        //     for x in s:
        //         if x == '(':
        //             res +=1
        //         if x == ')':
        //             res -=1
        //         if res <0:
        //             return False
        //     return res == 0
        char[] charArr = Arrays.copyOf(chars, chars.length);
        for (int i = 0, j = charArr.length; i < j; i++) {
            if (charArr[i] == ')') {
                return false;
            }
            if (charArr[i] == '(') {
                boolean flag = false;
                for (int m = i + 1, n = charArr.length; m < n; m++) {
                    if (charArr[m] == ')') {
                        charArr[m] = ' ';
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    return false;
                }
            }
        }
        return true;
    }
}
